/*
 * RouteScanner.java
 *
 * Created on April 5, 2007, 1:46 PM
 *
 * Copyright 2008 David D. Emory
 * 
 * This file is part of Five Points. See <http://www.fpdev.org> for
 * additional information regarding the project.
 * 
 * Five Points is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * Five Points is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with Five Points.  If not, see <http://www.gnu.org/licenses/>..
 */
package org.fpdev.core.algo.path;

import org.fpdev.core.routenet.RouteNetwork;
import org.fpdev.core.routenet.RNode;
import org.fpdev.core.routenet.RLinkBoard;
import org.fpdev.core.routenet.RLinkAlight;
import org.fpdev.core.routenet.RLink;
import org.fpdev.core.transit.*;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import org.fpdev.util.FPUtil;

/**
 *
 * @author demory
 */
public abstract class RouteScanner {

  protected RouteNetwork rteNet_;
  
  protected RNode origin_,  dest_;
  protected int time_; // the user-specified start/end time
  protected CalendarService service_;

  protected double walkSpeedFPS_;

  protected Set<RNode>[] reachableSets_;
  protected Map<RNode, List<RLink>>[] parents_;
  protected Map<RNode, Integer>[] nodeTimes_;

  protected Map<RNode, Set<RLink>> finalLinks_;
  protected List<List<RLink>> potentials_;

  protected int curLimit_;

  protected int bestTimeTT_,  bestTimeNT_;
  protected int bestStartTimeTT_,  bestStartTimeNT_;
  protected List<Integer> bestRunsTT_,  bestRunsNT_;
  protected List<RLink> bestPossibleTT_,  bestPossibleNT_;

  protected Set<String> validSubs_;

  protected final int FW = 1;
  protected final int BW = 2;

  /** Creates a new instance of RouteNavTree */
  public RouteScanner(RouteNetwork rteNet, Set<String> validSubs, RNode origin, RNode dest, int time, CalendarService service, double walkSpeedFPS) {
    rteNet_ = rteNet;
    validSubs_ = validSubs;
    origin_ = origin;
    dest_ = dest;
    time_ = time;
    service_ = service;
    walkSpeedFPS_ = walkSpeedFPS;
    //System.out.println("RS init w/ time "+time_+"/"+FPUtil.sTimeToStr(time_)+" fps "+walkSpeedFPS_);
  }

  public void execute() {

    finalLinks_ = new HashMap<RNode, Set<RLink>>();

    Iterator<RLink> endLinks = getPotentialFinalLinks();
    while (endLinks.hasNext()) {
      RLink link = endLinks.next();
      //System.out.println("Potential flink: "+link.getID());
      if (link.getType() == getFinalLinkType()) {
        addFinalLink(nodeEncounteredFirst(link), link);
        //System.out.println(" ADDED, nEF: "+nodeEncounteredFirst(link).getID());
      }
    }

    reachableSets_ = new Set[6];
    for (int i = 0; i < 6; i++) {
      reachableSets_[i] = new HashSet<RNode>();
    }

    parents_ = new Map[6];
    for (int i = 0; i < 6; i++) {
      parents_[i] = new TreeMap<RNode, List<RLink>>();
    }

    nodeTimes_ = new Map[6];
    for (int i = 0; i < 6; i++) {
      nodeTimes_[i] = new TreeMap<RNode, Integer>();
    }

    reachableSets_[0].add(startScanNode());
    nodeTimes_[0].put(startScanNode(), new Integer(time_));

    //System.out.println("Total rnodes: "+rteNet_.nodeCount());

    int bestTime = Integer.MAX_VALUE;
    List<RLink> bestPossible = null;
    List<Integer> bestRuns = null;
    int bestStartTime = 0;
    boolean foundBestNT = false;

    for (int i = 1; i < 5; i++) {
      potentials_ = new LinkedList<List<RLink>>();
      initPass();
      buildSet(i);
      System.out.println("rSet["+i+"] size: "+reachableSets_[i].size());
      Iterator<List<RLink>> pIter = potentials_.iterator();

      int pi = 0; // potential trip index

      while (pIter.hasNext()) {
        boolean dbg = false; // (i==3 && pi==2);
        List<RLink> rlinks = pIter.next();
        Iterator<RLink> rlIter = rlinks.iterator();
        List<Integer> theseRuns = new LinkedList<Integer>();
        int arrTime = (getType() == FW) ? time_ : ((RouteScannerBW) this).getStartTime(pi);
        if (dbg) {
          System.out.println("I3/P2: arrTime=" + FPUtil.dtime(arrTime));
        }
        int tripLenSec = 0;
        int startTime = arrTime;
        String prevSubID = (getType() == FW) ? "" : rlinks.get(0).getSubRoute().getFullID();

        if (rlinks.get(0).getType() == RLink.RLINK_BOARD) {
          double bsec = ((RLinkBoard) rlinks.get(0)).getAccessLenFt() / walkSpeedFPS_;
          arrTime += bsec;
          tripLenSec += bsec;
          if (dbg) {
            System.out.println(" bsec=" + bsec + " new arrtime=" + FPUtil.dtime(arrTime));
          }
        }

        String linkStr = "";
        int rli = 0; // route link index
        while (rlIter.hasNext()) {
          RLink rlink = rlIter.next();
          linkStr += rlink.getID() + ", ";
          int transferTime = (rlink.getSubRoute().getFullID().equals(prevSubID) || rli == 0) ? 0 : 60;
          int run = rlink.getSubRoute().getNextRun(service_, arrTime + transferTime, rlink.getStartDLI());
          if (run > 0) {
            int oldArrTime = arrTime;
            arrTime = rlink.getSubRoute().getTime(service_, run, rlink.getEndDLI() + 1);
            if (dbg) {
              System.out.println(" rlink=" + rlink.getID() + " new arrtime=" + FPUtil.dtime(arrTime) + " trtime=" + transferTime);
            }
            if (arrTime < oldArrTime) {
              System.out.println(" arrtime FUBAR");
            }
            theseRuns.add(new Integer(run));
          //tripLenSec += rlink.timeCostFW();
          } else {
            arrTime = tripLenSec = 100000000;
            break;
          }
          prevSubID = rlink.getSubRoute().getFullID();
          rli++;
        }
        if (rlinks.get(rlinks.size() - 1).getType() == RLink.RLINK_ALIGHT) {
          double alTime = ((RLinkAlight) rlinks.get(rlinks.size() - 1)).getAccessLenFt() / walkSpeedFPS_;
          //if(i==1) System.out.println(" alTime "+alTime);
          arrTime += alTime;
          if (dbg) {
            System.out.println(" alTime=" + alTime + " new arrtime=" + FPUtil.dtime(arrTime));
          }
        }
        if (getType() == BW) {
          arrTime += Math.abs(arrTime - time_);
        }
        //if(arrTime >= 100000000) System.out.println(" considered potential, not possible");
        //else {
        if (arrTime - startTime < 43200) {//100000000) {
          int thisTime = arrTime - startTime;
          //int thisTime = (getType() == FW ? arrTime : time_)-startTime;
          //if(thisTime<3600) {
            /*if(i==3) { 
          System.out.println(" considered potential "+pi+", len="+rlinks.size()+", time="+CUtil.elapsedTimeStr(thisTime));
          System.out.println("  startTime: "+CUtil.sTimeToStr(startTime));
          System.out.println("  pure trip len: "+CUtil.elapsedTimeStr(arrTime-startTime));
          }*/
          //}

          if (i == 1) {
            System.out.println("  links: " + linkStr);
          }
          if (thisTime > 0 && thisTime < bestTime) {
            if (i == 1) {
              System.out.println("  NEW BEST");
            }
            bestTime = thisTime;
            bestPossible = rlinks;
            bestRuns = theseRuns;
            bestStartTime = startTime;
          }
        }
        pi++;
      }

      if (bestPossible != null) {
        System.out.println("  Found on pass " + i + ", time=" + FPUtil.elapsedTimeStr(bestTime));
        Iterator<RLink> bpIter = bestPossible.iterator();
        String linkStr = "";

        /*int arrTime = (getType() == FW) ? time_ : time_-bestTime;
        if(bestPossible.get(0).getType() == CRouteLink.RLINK_BOARD)
        arrTime += ((CRouteLinkBoard) bestPossible.get(0)).getAccessLenFt()/walkSpeedFPS_;*/

        /*int bpi = 0;
        while(bpIter.hasNext()) {
        CRouteLink rlink = bpIter.next();
        linkStr += rlink.getID()+", ";
        bpi++;
        }
        System.out.println(" links: "+linkStr);*/
        bestTimeTT_ = bestTime;
        bestPossibleTT_ = bestPossible;
        bestStartTimeTT_ = bestStartTime;
        bestRunsTT_ = bestRuns;

        //startTime_ = getStartTime(i);
        //break;
        if (!foundBestNT) {
          bestTimeNT_ = bestTime;
          bestPossibleNT_ = bestPossible;
          bestStartTimeNT_ = bestStartTime;
          bestRunsNT_ = bestRuns;
          foundBestNT = true;
        }
      }

    }

  }

  protected void initPass() {
  }

  protected abstract int getFinalLinkType();

  protected abstract Iterator<RLink> getPotentialFinalLinks();

  protected abstract RNode startScanNode();

  protected abstract RNode nodeEncounteredFirst(RLink link);

  protected abstract int getType();

  protected int getStartTime(int pi) {
    return time_;
  }

  //protected int getEndTime
  public int getBestTimeTT() {
    return bestTimeTT_;
  }

  public int getBestStartTimeTT() {
    return bestStartTimeTT_;
  }

  public List<RLink> getBestRLinksTT() {
    return bestPossibleTT_;
  }

  public List<Integer> getBestRunsTT() {
    return bestRunsTT_;
  }

  public int getBestTimeNT() {
    return bestTimeNT_;
  }

  public int getBestStartTimeNT() {
    return bestStartTimeNT_;
  }

  public List<RLink> getBestRLinksNT() {
    return bestPossibleNT_;
  }

  public List<Integer> getBestRunsNT() {
    return bestRunsNT_;
  }

  private void addFinalLink(RNode node, RLink flink) {
    //System.out.println("adding final link "+flink.getID());
    if (finalLinks_.containsKey(node)) {
      finalLinks_.get(node).add(flink);
    } else {
      Set<RLink> set = new HashSet<RLink>();
      set.add(flink);
      finalLinks_.put(node, set);
    }
  }

  private void buildSet(int limit) {
    Iterator<RNode> nodes = reachableSets_[limit - 1].iterator();
    curLimit_ = limit;
    while (nodes.hasNext()) {
      RNode node = nodes.next();
      int time = nodeTimes_[limit - 1].get(node).intValue();
      addToSet(node, time); //, reachableSets_[limit], parents_[limit]);
    }
  }

  protected abstract void addToSet(RNode rNode, int time);
}
